﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 实验报告3._1
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkList<int> link = new LinkList<int>();
            link.Append(8);
            link.Append(12);
            link.Append(10);
            link.Append(18);
            Console.WriteLine("初始化链表:");
            link.DisplayItems();
            Console.WriteLine("在链表的第3个节点前插入14初始化链表:");
            link.InsertAt(14, 3);
            link.DisplayItems();
            Console.WriteLine("查找指定元素10");
            Console.WriteLine(link.IndexOf(10)); 
            Console.WriteLine("取链表第3个节点的元素");
            Console.WriteLine(link.GetNode(3));
            Console.WriteLine("删除链表的第2个节点后的链表:");
            link.RemoveAt(2);
            link.DisplayItems();
           
            Console.ReadKey();
        }
    }
    public class LinkNode<T>
    {
        private T data;
        private LinkNode<T> next;
        public LinkNode(T val, LinkNode<T> p)
        {
            data = val;
            next = p;
        }
        public LinkNode(LinkNode<T> p)
        {
            next = p;
        }
        public LinkNode(T val)
        {
            data = val;
            next = null;
        }
        public LinkNode()
        {
            data = default(T);
            next = null;
        }
        public T Data
        {
            get
            {
                return data;
            }
            set
            {
                data = value;
            }
        }
        public LinkNode<T> Next
        {
            get
            {
                return next;
            }
            set
            {
                next = value;
            }
        }
    }
    public class LinkList<T> : LinkNode<T>
    {
        private LinkNode<T> first;
        public LinkList()
        {
            first = null;
        }
        public LinkNode<T> FIRST
        {
            get { return first; }
            set { first = value; }
        }
        public bool IsEmpty
        {
            get
            {
                if (first == null) { return true; }
                else return false;
            }
        }
        public int Count
        {
            get
            {
                int i = 0;
                LinkNode<T> node = first;
                while (node.Next != null)
                {
                    node = node.Next;
                    i++;
                }
                return i;
            }
        }
        public LinkNode<T> GetNode(int pos)
        {
            LinkNode<T> node = first;
            for (int i = 0; i < pos; i++)
            {
                if (node.Next == null)
                {
                    throw new IndexOutOfRangeException();
                }
                node = node.Next;
            }
            return node;
        }
        public int IndexOf(T value)
        {
            if (IsEmpty)
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            LinkNode<T> p = new LinkNode<T>();
            p = first;
            int i = 1;
            while (!p.Data.Equals(value) && p.Next != null)
            {
                p = p.Next;
                ++i;
            }
            return i;
        }
        public T RemoveAt(int i)
        {
            if (IsEmpty || i < 0)
            {
                Console.WriteLine("Link is empty or Position is error!");
                return default(T);
            }
            LinkNode<T> q = new LinkNode<T>();
            if (i == 1)
            {
                q = first;
                first = first.Next;
                return q.Data;
            }

            LinkNode<T> p = first;
            int j = 1;
            while (p.Next != null && j < i)
            {
                j++;
                q = p;
                p = p.Next;
            }
            if (j == i)
            {
                q.Next = p.Next;
                return p.Data;
            }
            else
            {
                Console.WriteLine("The ith node is not exist!");
                return default(T);
            }
        }
        public void InsertAt(T item, int i)
        {
            if (IsEmpty || i < 1)
            {
                Console.WriteLine("List is empty or Position is error!");
                return;
            }
            if (i == 1)
            {
                LinkNode<T> q = new LinkNode<T>(item);
                q.Next = first;//链表的新增节点的引用域为空即该链表是最后一个节点
                first = q;//在第一个节点的前面插入q所以第一个节点变为q，而head引用需要修改为q，因为head
                //永远都是指向第一个节点的引用，头结点指向新增节点的引用域即该节点也是该链表的第一个节点
                return;
            }
            // 遍历直到当前结点的位置为i
            // 如果插入位置超过单链表长度，则插入失败
            else
            {

                LinkNode<T> p = first;//初始化为头结点,遍历的起点节点,p保存第i个节点的引用
                LinkNode<T> pre = new LinkNode<T>();//p的前一个节点
                int j = 1;
                // 遍历直到当前结点的位置为i
                // 如果插入位置超过单链表长度，则插入失败
                while (p.Next != null && j < i)
                {
                    pre = p;
                    p = p.Next;
                    j++;
                }
                if (j == i)
                {
                    LinkNode<T> node = new LinkNode<T>(item);
                    node.Next = p;
                    pre.Next = node;
                }
            }
        }
        public void Append(T item)
        {
            LinkNode<T> q = new LinkNode<T>(item);//待添加的节点引用域
            LinkNode<T> p = new LinkNode<T>();//最后一个节点的引用域
            // 判断此时是否为空表，是则直接修改头结点的引用域
            if (first == null)
            {
                first = q;
                return;
            }
            // 不是则遍历结点，找到最后最后一个结点,则head为第一个节点，head.Next为第二个节点的引用
            else
            {
                p = first;//从头结点才开始遍历
                while (p.Next != null)
                {
                    p = p.Next;// 设置最后一个结点的引用域为追加数据元素的地址
                }
                p.Next = q;
            }
        }
        public void DisplayItems()
        {
            // 判断是否为空表
            if (IsEmpty)
            {
                Console.WriteLine("单链表表中不存在数据元素，无法执行打印操作，操作失败！");
            }
            // 执行打印操作
            else
            {
                LinkNode<T> p = new LinkNode<T>();
                p = first;
                while (p.Next != null)
                {
                    Console.Write(p.Data + "\t");
                    p = p.Next;
                }
                // 打印最后一个结点
                Console.Write(p.Data + "\t");
                Console.WriteLine();
            }
        }
    }
}

  